/**
 * Copyright (C) 2001-2017 wxyz <hyhjwzx@126.com>
 * <p>
 * This program can be distributed under the terms of the GNU GPL Version 2.
 * See the file LICENSE.
 */
package ren.wxyz.algorithm.dsaj2.chap02;

/**
 * 有序数组
 *
 * @author wxyz 2017-02-16_22:11
 * @since 1.0
 */
public class OrdArray {
    private long[] a;
    private int nElems;

    public OrdArray(int max) {
        this.a = new long[max];
        nElems = 0;
    }

    public int size() {
        return nElems;
    }

    /**
     * 查找值的位置
     *
     * @param searchKey 要查找的值
     * @return
     */
    public int find(long searchKey) {
        // 第一个位置
        int lowerBound = 0;
        // 最后一个位置
        int upperBound = nElems - 1;

        // 当前位置
        int currIn;

        while (true) {
            currIn = (lowerBound + upperBound) / 2;
            if (a[currIn] == searchKey) {
                return currIn;
            }
            else if (lowerBound > upperBound) {
                return nElems;
            }
            else {
                if (a[currIn] < searchKey) {
                    lowerBound = currIn + 1;
                }
                else {
                    upperBound = currIn - 1;
                }
            }
        }
    }

    /**
     * 将一个值插入有序数组
     *
     * @param value 要插入的值
     * @return
     */
    public boolean insert(long value) {
        if (nElems == a.length) {
            return false;
        }

        if (nElems == 0) {
            a[0] = value;
            nElems++;
            return true;
        }

        // 第一个位置
        int lowerBound = 0;
        // 最后一个位置
        int upperBound = nElems - 1;

        // 当前位置
        int currIn;
        if (value < a[lowerBound]) {
            currIn = -1;
        }
        else if (a[upperBound] <= value) {
            currIn = upperBound;
        }
        else {
            while (true) {
                currIn = (lowerBound + upperBound) / 2;
                if (a[currIn] == value) {
                    break;
                }
                else if (lowerBound > upperBound) {
                    break;
                }
                else {
                    if (a[currIn] < value) {
                        lowerBound = currIn + 1;
                    }
                    else {
                        upperBound = currIn - 1;
                    }
                }
            }
        }

        int insertPos = currIn + 1;
        if (insertPos == nElems) {
            a[insertPos] = value;
            nElems++;
            return true;
        }

        for (int i = ++nElems; i > insertPos; i--) {
            a[i] = a[i - 1];
        }

        a[insertPos] = value;
        return true;
    }

    /**
     * 删除一个值
     *
     * @param value 要删除的值
     * @return
     */
    public boolean delete(long value) {
        if (nElems == 0) {
            return false;
        }

        int deletePos = find(value);
        if (deletePos == nElems) {
            return false;
        }

        nElems--;
        for (int i = deletePos; i < nElems; i++) {
            a[i] = a[i + 1];
        }

        return true;
    }

    /**
     * 展示有序数组内容
     */
    public void display() {
        for (int i = 0; i < nElems; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    /**
     * 测试方法
     * @param args
     */
    public static void main(String[] args) {
        OrdArray oa = new OrdArray(50);

        oa.insert(20);
        oa.insert(10);
        oa.insert(300);
        oa.display();

        oa.insert(50);
        oa.insert(15);
        oa.insert(35);
        oa.insert(50);
        oa.display();

        oa.delete(50);
        oa.delete(35);
        oa.display();
    }
}
